\documentclass[a4paper]{ctexart}
\usepackage[hidelinks]{hyperref}%目录
\usepackage{listing}
\usepackage{xeCJK} %导入这个宏包，就可以支持中文
\usepackage{cite}%文献引用
\usepackage{graphicx}
\usepackage{amsthm,amsmath,amssymb,amsfonts}%数学命题，数学字母，排版
\usepackage[a4paper,left=25.4mm,right=25.4mm,top=29.8mm,bottom=29.8mm]{geometry}

\pagestyle{myheadings}
\numberwithin{equation}{section}%以section编号equation




%数学命题环境定义 
%证明环境直接用proof
\theoremstyle{plain} \newtheorem{thm}{定理}[section]
\theoremstyle{plain} \newtheorem*{lemma}{引理}
\theoremstyle{plain} \newtheorem*{prop}{prop}
\theoremstyle{plain} \newtheorem*{property}{性质}
\theoremstyle{definition} \newtheorem*{define}{定义}
\theoremstyle{plain} \newtheorem*{cor}{cor}
\theoremstyle{plain} \newtheorem*{eg}{例}
\theoremstyle{plain} \newtheorem{axiom}{公理}
\theoremstyle{remark} \newtheorem*{rmk}{Rmk}
\theoremstyle{plain} \newtheorem*{goal}{Goal}

\title{Data Structure}
\author{陈宇涛,强数2101,3210102287}

\begin{document}
\maketitle

\section*{BST sorting}
\markright{Data Structure}




\subsection*{设计思路}



\begin{flushleft}
    (1)~二叉搜索树\\
     ~~~对于二叉搜索树,我们采取了数据结构书中的class BinarySearchTree的算法。对于一组数据我们只需要按照顺序要求一一插入二叉树中,而后从左至右依次输出这组数据便能够实现升序排列的效果。\\
    ~~~二叉树的具体要求如下：\\
    1.每一个叶子节点x都只会有一个左叶子节点(左孩子)z,一个右叶子节点(右孩子)y.\\
    2.任意一个节点x的左节点下的所有节点结构称为x的左子树,同理右节点下的所有节点结构称为右子树:需要满足左子树中任意节点值z,~$z<x$~,且右子树中的任意节点值y,~$x<y$.\\
    3.所有节点值各不相同.\\
    ~\\
    (2)~ 理论内容 ~\\
    ~~~理论上程序对于插入的数据insert()的运行次数和二叉树的高度height有很大关系,
    所以按照理论来说对于最好的用户输入数据方式是完全左右平衡,即较大的数据在数组中间，较小的数据在数组的头尾；
    最差的输入情况就是用户将已经升序或者降序的顺序排列好的数组再次进入二叉树排序，这样的运行时间$t = \Theta(n^{2})$.而对于一般的随机排列的数据,它运行的平均时间为$t = \Theta(n\log{n})$.\\
    ~\\
\end{flushleft}

\subsection*{测试说明}


\begin{eg}
\begin{flushleft}
    ~\\
    (1)~~测试过程\\
    1.~验证能够正确排序输出,包括用户输入了重复数据。直接 make ./test及可以看到对于数组$\left[3,4,9,3,2,3\right] $的升序输出结果为2,3,4,9\\
    2.~在终端中输入bash run, 即可以查看下面6组测试数据的本次运行时间结果。\\

    \newpage

    (2)~~测试数据\\
    我选取几组数据进行了样例分析,来验证在设计思路中所说的二叉树排序算法的特性,结果如下表所示:\\
    \begin{table}[!ht]
        \centering
        \begin{tabular}{|l|l|l|l|l|l|}
        \hline
            测试序号 & 数据规模 & 数据内容 & 排列顺序 & 测试次数 & 平均运行时间 \\ \hline
            1 & $10^{3}$ & 1-1K & 升序 & 10 & $1.11 \cdot 10^{-4}$秒 \\ \hline
            2 & $10^{3}$ & -500-500 & 随机 & 10 & $9.39 \cdot 10^{-5}$秒 \\ \hline
            3 & $10^{4}$ & -5K-5K & 升序 & 10 & $1.34 \cdot 10^{-3}$秒 \\ \hline
            4 & $10^{4}$ & -5K-5K & 随机 & 10 & $1.28 \cdot 10^{-3}$秒 \\ \hline
            5 & $10^{5}$ & 1-100K & 升序 & 10 & 25.3839秒 \\ \hline
            6 & $10^{5}$ & -50K-50K & 随机 & 10 & 0.03541秒 \\ \hline
        \end{tabular}
    \end{table}

    ~\\

    (3)~~测试分析\\
    ~~~可以发现对于10次测试平均来说，在$10^{5}$的数据规模时，随机排序和升序排序的输入数组的运行时间有了很大的差别，整整差了三个数量级，这也符合$\frac{\Theta(n^{2})}{\Theta(n\log(n))}$的比值。而在$10^{4}$以下的数量级几乎没有什么区别。\\

    ~\\

    (4)~~平衡树\\
    ~~~我们可以看到这种由于用户输入数组顺序所造成的运行时间在大规模数据下的巨大差异是不可接受的。在本次测试中采用的是提前进行一次随机排序的方法，基本避免了输入的数据是已经升序或降序的情况，从而加大了运行效率。\\
    ~~~但是这样的运行效率依然有不小的改进空间，由于插入时insert()递归调用的次数和树的高度有很大关系，所以考虑平衡树排序算法来保证每次插入都不会导致树向左或向右偏倒以达到最好的排序效率。\\



\end{flushleft}
\end{eg}

\end{document}